﻿#pragma once

#include <iostream>
#include <cassert>
#include <mutex>
#include <unordered_map>
#include <windows.h>
#include <vector>
#include <thread>
#include <atomic>
#include <algorithm>
#include "FixedLenMemPool.h"
using std::cout;
using std::endl;

static const int MaxFreeListSize = 208;
static const int MaxSize = 256 * 1024;
static const int Npages = 129;
static const int SysPageSize = 8 * 1024;
static const int Nshift = 13;

struct Span;
static ObjectPool<Span> g_objPool;

#ifdef _WIN64
typedef unsigned long long PageSize; //页的id范围

#elif _WIN32
typedef size_t PageSize;

#else

#endif

#ifdef _WIN64
#define BitNum 64

#elif _WIN32
#define BitNum 32

#else

#endif

//inline static void* SystemAlloc(size_t kpage)
//{
//
//#ifdef _WIN32
//	void* ptr = VirtualAlloc(0, kpage * (1 << Nshift), MEM_COMMIT | MEM_RESERVE,
//		PAGE_READWRITE);
//#else
//	// linux下brk mmap等
//#endif
//	if (ptr == nullptr)
//		throw std::bad_alloc();
//
//	return ptr;
//}

inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap等
#endif
}

static void*& nextobj(void* cur)
{
	return *(void**)cur;
}

class FreeList
{
private:
	void* _freelist;
	size_t _size;
	size_t _objnum;

public:

	FreeList()
		:_freelist(nullptr)
		,_size(1)
		,_objnum(0)
	{}

	size_t& FMaxSize()
	{
		return _size;
	}

	size_t ObjNum()
	{
		return _objnum;
	}

	void RangeInsert(void*& start, void*& end, int num)
	{
		assert(start && end);

		nextobj(end) = _freelist;
		_freelist = start;

		_objnum += num;
	}

	void RangePop(void*& start, void*& end, size_t num)
	{
		assert(_objnum >= num);
		end  = start = _freelist;
		
		for (size_t i = 0; i < num - 1; ++i)
		{
			end = nextobj(end);
		}

		_freelist = nextobj(end);
		nextobj(end) = nullptr;	
		_objnum -= num;
	}

	void push(void* obj)
	{
		nextobj(obj) = _freelist;
		_freelist = obj;

		++_objnum;
	}

	void* pop()
	{
		void* obj = _freelist; 
		_freelist = nextobj(_freelist);;

		--_objnum;
		return obj;
	}

	bool Empty()
	{
		return _freelist == nullptr;
	}
};

struct Span
{
	PageSize page_id; //页的起始号码
	size_t _n;        //页数

	Span* _prev;
	Span* _next;

	void* _freelist;
	size_t _usecount;

	bool isUse;
	size_t _objSize;

	Span()
		:page_id(0)
		,_n(0)
		,_prev(nullptr)
		,_next(nullptr)
		,_freelist(nullptr)
		,_usecount(0)
		,isUse(false)
		,_objSize(0)
	{}
};

//双向带头循环链表
class SpanList
{
private:
	Span* _head;

public:
	std::mutex _mutex;

public:
	SpanList()
	{
		//_head = new Span();
		_head = g_objPool.New();
		_head->_next = _head;
		_head->_prev = _head;
	}

	void Insert(Span* pos, Span* newspan)
	{
		assert(pos && newspan);
		
		Span* prev = pos->_prev;
		
		newspan->_prev = prev;
		newspan->_next = pos;
		prev->_next = newspan;
		pos->_prev = newspan;
	}

	void Erase(Span* span)
	{
		assert(span && span != _head);

		Span* prev = span->_prev;
		Span* next = span->_next;

		prev->_next = next;
		next->_prev = prev;
	}

	bool Empty()
	{
		return _head->_next == _head;
	}

	Span* PopFront()
	{
		Span* span = begin();
		Erase(span);
		return span;
	}

	void PushFront(Span* span)
	{
		Insert(begin(), span);
	}

	Span* begin()
	{
		return _head->_next;
	}

	Span* end()
	{
		return _head;
	}
};


class Caculate
{
public:

	// [1,128]                8byte对⻬       freelist[0,16)
	// [128+1,1024]           16byte对⻬      freelist[16,72)
	// [1024+1,8*1024]        128byte对⻬     freelist[72,128)
	// [8*1024+1,64*1024]     1024byte对⻬    freelist[128,184)
	// [64*1024+1,256*1024]   8*1024byte对⻬  freelist[184,208)

	//1~128字节，按照8字节对齐，1字节分8字节空间，9字节分16字节空间，这个区段对应一个自由链表区段
	//RoundUp就是计算给出size，应该分配多少字节空间
	static size_t _RoundUp(size_t size, size_t align)
	{
		return ((size + align - 1) & ~(align - 1)); //对于频繁调用的计算函数，位运算更高效
	}

	static size_t RoundUp(size_t size)
	{
		if (size <= 128)
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _RoundUp(size, 8 * 1024);
		}
		else
		{
			return _RoundUp(size, 1 >> Nshift);
		}

		return -1;
	}

public:

	//通过申请内存的大小计算出要映射到哪个自由链表
	static size_t _Index(size_t size, size_t align)
	{
		return ((size + (1 << align) - 1) >> align) - 1;
	}

	static size_t Index(size_t size)
	{
		assert(size <= MaxSize);

		int group_size[4] = { 16, 72, 128, 184 };
		
		if (size <= 128)
		{
			return _Index(size, 3);
		}
		else if (size <= 1024)
		{
			return _Index(size - 128, 4) + group_size[0];
		}
		else if (size <= 8 * 1024)
		{
			return _Index(size - 1024, 7) + group_size[1];
		}
		else if (size <= 64 * 1024)
		{
			return _Index(size - 8 * 1024, 10) + group_size[2];
		}
		else if (size <= 256 * 1024)
		{
			return _Index(size - 64 * 1024, 13) + group_size[3];
		}
		else
		{
			assert(false);
		}

		return -1;
	}

public:

	//确定ThreadCache申请内存对象的上下限，计算出合适的申请大小
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0 && size <= MaxSize);

		size_t num = MaxSize / size;
		if (num < 2) num = 2;
		if (num > 512) num = 512;

		return num;
	}

public:

	//计算给一个Span多少页合适，根据内存对象大小size
	static size_t NumPageSize(size_t size)
	{
		//num --- 内存对象数
		size_t num = NumMoveSize(size);
		//memsize --- 这些内存对象的总大小
		size_t memsize = num * size;
		//计算这些内存对象需要多少页
		size_t pagesize = memsize >> Nshift; //右移13位，即除以8 * 1024
		if (pagesize < 1)
			pagesize = 1;

		return pagesize;
	}
};
